package skiplist

import (
	"math/rand"
	"reflect"
)

const (
	// 跳表的最大层数
	LEVEL_MAX = 16
	// 跳表的概率因子
	LEVEL_INCR_RATE = 0.5
)

// element +++++++++++++++++++++++++++++++++++++++++++++++

// 定义跳表节点
type Element struct {
	// 节点值
	Value interface{}
	// 节点的前向指针， 之所以使用切片，是因为跳表是多层的
	// 每一层都有一个前向指针，指向下一层的节点
	// 例如，level=3的节点有3个前向指针，分别指向level=2、level=1、level=0的节点
	// 这里的level表示跳表的层数
	// 此处切片的长度是跳表的最大层数
	// 例如，跳表的最大层数是4，那么切片的长度就是4
	Forward []*Element
	// 节点的后向指针，只是第一层的后向指针
	Backward *Element
	// 节点的分值，类似Redis的ZSET中的分值，可以用来进行排序、按区间查询等操作
	Score int64
}

// 节点的构造函数
func NewElement(score int64, value interface{}, level int) *Element {
	// 创建一个新的节点
	e := &Element{
		Value:    value,
		Score:    score,
		Forward:  make([]*Element, level),
		Backward: nil,
	}
	return e
}

// 定义Next函数用来获取节点的下一个节点
func (e *Element) Next() *Element {
	// 返回节点的下一个节点
	if e == nil {
		return nil
	}
	return e.Forward[0]
}

// 定义Prev函数用来获取节点的上一个节点
func (e *Element) Prev() *Element {
	// 返回节点的上一个节点
	if e == nil {
		return nil
	}
	return e.Backward
}

// element -------------------------------------------------

// skiplist +++++++++++++++++++++++++++++++++++++++++++++++

// 定义跳表
// header 是一个哑节点作为跳表的头节点
// level 是跳表中所有节点的最大层数
// length 是跳表中节点的数量
type SkipList struct {
	// 跳表的头节点，头结点的level是最大层数
	header *Element
	// 跳表的最大层数
	level int
	// 跳表的节点数量
	length int
	// 跳表的最大层数
	maxLevel int
	// 跳表的随机数生成器
	// 用于生成随机的层数
	// 这里使用的是一个简单的随机数生成器
	// 你可以根据需要替换成更复杂的随机数生成器
	randomGenerator func(int, float32) int
}

// 跳表的构造函数
func NewSkipList(maxLevel int) *SkipList {
	// 创建一个新的跳表
	s := &SkipList{
		header:          NewElement(0, nil, maxLevel),
		level:           0, // 跳表的当前的最大实际层数
		length:          0, // 跳表的当前的节点数量
		maxLevel:        maxLevel,
		randomGenerator: randomLevel,
	}
	return s
}

// 定义Front函数用来获取跳表的首节点
func (s *SkipList) Front() *Element {
	// 返回跳表的头节点的下一个节点
	return s.header.Forward[0]
}

// 定义Length函数用来获取跳表的节点数量
func (s *SkipList) Length() int {
	// 返回跳表的节点数量
	return s.length
}

// Search方法用来在跳表中查找一个指定score值的节点
// 如果找到，返回节点的值和分值
// 如果没有找到，返回nil
func (s *SkipList) Search(score int64) (*Element, bool) {
	// 从跳表的头节点开始查找
	current := s.header
	// 从跳表的最高层开始查找，一层一层的往下查找，直到最后一层
	for i := s.level - 1; i >= 0; i-- {
		// 遍历当前层的所有节点，找到最后一个小于等于score的节点
		// 如果当前节点的下一个节点的分值小于要查找的分值，则向右移动（也就是current=current.Forward[i]）
		// 否则，向下移动（也就是i的值递减）
		for current.Forward[i] != nil && current.Forward[i].Score < score {
			current = current.Forward[i]
		}
	}
	// 查找完毕，返回当前节点的下一个节点
	current = current.Forward[0]
	if current != nil && current.Score == score {
		return current, true
	}
	return nil, false
}

// Insert方法用来在跳表中插入一个新的节点
// 如果插入成功，返回true
// 如果插入失败，返回false
// 插入失败的原因可能是插入的数据类型不合法
// 当前实现不允许score和value有重复的值，简单起见!!!
func (s *SkipList) Insert(score int64, value interface{}) bool {
	// value的类型必须是可比较是否相等的类型，否则返回false
	if value == nil {
		return false
	}
	if !isComparable(value) {
		return false
	}

	// 遍历跳表的所有节点，找到插入的位置，这个过程中要记录目标节点在每一层的前一个节点，因为每一层的前向指针都有可能发生变化
	update := make([]*Element, s.maxLevel)
	current := s.header
	for i := s.level - 1; i >= 0; i-- {
		// 遍历当前层的所有节点，找到最后一个小于等于score的节点
		for current.Forward[i] != nil && current.Forward[i].Score < score {
			current = current.Forward[i]
		}
		update[i] = current
	}
	// 查找完毕，返回当前节点的下一个节点
	current = current.Forward[0]
	// 如果当前节点的分值等于要插入的分值，说明已经存在这个节点了，返回false
	if current != nil && current.Score == score {
		return false
	}
	// 生成一个随机的层数
	level := s.randomGenerator(s.maxLevel, LEVEL_INCR_RATE)
	// 如果生成的层数大于跳表的当前的最大层数，我们仅增加一层
	// 而且增加的每一层都需要头节点指向过来,所以update中要存储这基层的位置节点
	if level > s.level {
		level = s.level + 1
		update[s.level] = s.header
		s.level = level
	}
	// 创建一个新的节点
	newElement := NewElement(score, value, level)
	// 更新新节点的前向指针
	for i := 0; i < level; i++ {
		newElement.Forward[i] = update[i].Forward[i]
		update[i].Forward[i] = newElement
	}
	// 更新新节点的后向指针
	newElement.Backward = update[0]
	// 更新新节点的前向节点的后向指针
	if newElement.Forward[0] != nil {
		newElement.Forward[0].Backward = newElement
	}

	// 更新跳表的节点数量
	s.length++
	// 返回true表示插入成功
	return true
}

// Delete方法用来在跳表中删除一个指定score值的节点
// 如果删除成功，返回true
// 如果删除失败，返回false
// 删除失败的原因可能是删除的数据类型不合法
// 当前实现不允许score和value有重复的值，简单起见!!!
func (s *SkipList) Delete(score int64) bool {
	// Delete和Insert类似，遍历跳表的所有节点，找到删除的位置，这个过程中要记录目标节点在每一层的前一个节点，因为每一层的前向指针都有可能发生变化
	update := make([]*Element, s.maxLevel)
	current := s.header
	for i := s.level - 1; i >= 0; i-- {
		// 遍历当前层的所有节点，找到最后一个小于等于score的节点
		for current.Forward[i] != nil && current.Forward[i].Score < score {
			current = current.Forward[i]
		}
		update[i] = current
	}
	// 查找完毕，返回当前节点的下一个节点
	current = current.Forward[0]
	// 如果当前节点的分值等于要删除的分值，说明找到了这个节点了
	if current != nil && current.Score == score {
		// 根据当前节点的前向指针切片，逐个更新前向节点的后向指针
		for i := 0; i < len(current.Forward); i++ {
			// 更新前向节点的后向指针
			if update[i].Forward[i] == current {
				update[i].Forward[i] = current.Forward[i]
			}
			// 更新后向节点的前向指针
			if current.Forward[0] != nil {
				current.Forward[0].Backward = update[0]
			}
		}

		// 更新跳表的节点数量
		s.length--
		return true
	}
	// 如果没有找到这个节点，返回false
	return false
}

// Get方法用来在跳表中获取一个指定score值的节点
// 如果获取成功，返回节点的值和分值
// 如果没有找到，返回nil
// 获取节点的值和分值
// 这里的实现是直接返回节点的值和分值
// 你可以根据需要修改成返回节点的指针
func (s *SkipList) Get(score int64) (*Element, bool) {
	// 从跳表的头节点开始查找
	current := s.header
	// 从跳表的最高层开始查找，一层一层的往下查找，直到最后一层
	for i := s.level - 1; i >= 0; i-- {
		// 遍历当前层的所有节点，找到最后一个小于等于score的节点
		for current.Forward[i] != nil && current.Forward[i].Score < score {
			current = current.Forward[i]
		}
	}
	// 查找完毕，返回当前节点的下一个节点
	current = current.Forward[0]
	if current != nil && current.Score == score {
		return current, true
	}
	return nil, false
}

// skiplist ---------------------------------------------------

// util function ++++++++++++++++++++++++++++++

// 定义一个随机数生成器
// 这个随机数生成器用来生成跳表的层数
// 例如，跳表的最大层数是16，那么这个随机数生成器就会生成一个[1,16]之间的随机整数，其中rate表示概率
// 例如，rate=0.5表示50%的概率增加一层，所以返回的层数为2的概率是50%，返回的层数为3的概率是25%，返回的层数为4的概率是12.5%，返回的层数为5的概率是6.25%
func randomLevel(maxLevel int, rate float32) int {
	max := int(rate * 100) // 将rate转换成百分比
	// 这里的max可以根据需要调整
	// rand.Intn(100) 返回[0,100)之间的随机整数
	// 此处的max表示概率，比如max=50表示50%的概率增加一层，此时 rate=0.5
	// 如果你想要更高的概率增加一层，可以改成0.75
	// 如果你想要更低的概率增加一层，可以改成0.25

	// 生成一个随机的层数
	level := 1
	for level < maxLevel && rand.Intn(100) <= max {
		level++
	}
	return level
}

func randomLevelRate(maxLevel int, rate float32) int {
	// 生成一个随机的层数
	level := 1
	// rand.Float32() 返回[0,1)之间的随机浮点数
	// 这里的rate可以根据需要调整
	// 例如，如果你想要更低的概率增加一层，可以改成0.25
	for level < maxLevel && rand.Float32() < rate {
		level++
	}
	return level
}

// 判断一个 interface{} 是否是可比较的类型
func isComparable(value interface{}) bool {
	if value == nil {
		return false // nil 是不可比较的
	}
	typ := reflect.TypeOf(value)
	return typ.Comparable() // 使用 reflect.Type 的 Comparable 方法
}

// util function ------------------------------
